﻿#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main()
{
    int n, m;
    cin >> n >> m;
    int ret = n;
    for (int i = 0; i < m - 1; i++)
    {
        ret = ret * (n - 1) % 109;
    }
    cout << ret << endl;
    return 0;
}

class Solution
{
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
    {
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
        heap.push(startEnd[0][1]); // 先把第⼀个区间放进去
        for (int i = 1; i < n; i++) // 处理剩下的区间
        {
            int a = startEnd[i][0], b = startEnd[i][1];
            if (a >= heap.top()) // 没有重叠
            {
                heap.pop();
                heap.push(b);
            }
            else // 有重叠
            {
                heap.push(b); // 重新安排⼀个⼈
            }
        }
        return heap.size();
    }
};

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
int x1, y1, x2, y2;
char arr[N][N];
int dist[N][N]; // 作用：判断[i, j] 位置是否已经搜索过，以及到达 [i, j] 位置的最短距离
int bfs()
{
    if (arr[x2][y2] == '*') return -1;

    memset(dist, -1, sizeof(dist)); // 表⽰还没开始搜索
    queue<pair<int, int>> q;
    q.push({ x1, y1 });
    dist[x1][y1] = 0;
    while (q.size())
    {
        //auto [a, b] = q.front();
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            //合法坐标                                   //可以走
            if (x >= 1 && x <= n && y >= 0 && y <= m && arr[x][y] == '.' &&
                //没有被搜索过
                dist[x][y] == -1)
            {
                q.push({ x, y });
                //计算长度
                dist[x][y] = dist[a][b] + 1;
                if (x == x2 && y == y2) return dist[x2][y2];
            }
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}